/**
 * 给定一个整数 n 和一个 无重复 黑名单整数数组blacklist。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个未加入黑名单blacklist的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。
 *
 * 优化你的算法，使它最小化调用语言 内置 随机函数的次数。
 *
 * 实现Solution类:
 *
 * Solution(int n, int[] blacklist)初始化整数 n 和被加入黑名单blacklist的整数
 * int pick()返回一个范围为 [0, n - 1] 且不在黑名单blacklist 中的随机整数
 *
 * 链接：https://leetcode.cn/problems/random-pick-with-blacklist
 */
class Pick {
    int sz;
    Map<Integer,Integer> map;
    Random rand=new Random();
    public Pick(int n, int[] blacklist) {
        int len=blacklist.length;
        sz=n-len;
        map=new HashMap<>();
        for(int b:blacklist) {
            map.put(b,-1);
        }
        int last=n-1;
        for(int b:blacklist) {
            // 如果 b 已经在区间 [sz, N)
            // 可以直接忽略
            if(b>=sz) {
                continue;
            }
            while(map.containsKey(last)) {
                last--;
            }
            map.put(b,last);
            last--;
        }
    }
    
    public int pick() {
        // 随机选取一个索引
        int index=rand.nextInt(sz);
        // 这个索引命中了黑名单，
        // 需要被映射到其他位置
        if(map.containsKey(index)) {
            return map.get(index);
        }
         // 若没命中黑名单，则直接返回
        return index;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(n, blacklist);
 * int param_1 = obj.pick();
 */